import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User:xieChao
 * Date:2022/10/14 13:08
 */
public class TopK {
    /**
     * 解决TopK问题
     * 求数组中前k个最小元素
     * @param array
     * @param k
     * @return
     */
    public static int[] topK(int[] array,int k){
        //1.创建一个大小为K的大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //2.遍历数组，放k个元素创建大根堆
        for (int i = 0; i < array.length; i++) {
            if(maxHeap.size() < k){
                maxHeap.offer(array[i]);
            }else{
                //3.从第k+1个元素开始，每个元素和大根堆的堆顶元素比较
                int top = maxHeap.peek();
                if(top > array[i]){
                    maxHeap.poll();//3.1,先弹出
                    maxHeap.offer(array[i]);//3.2，再比较
                }
            }
        }
        /**
         * 接受最后的结果
         */
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = maxHeap.poll();
        }
        return tmp;
    }

    public static void main(String[] args) {
        int[] array = {18,21,8,10,34,12};
        System.out.println(Arrays.toString(topK(array, 3)));
        System.out.println("====================================");
        Arrays.sort(array,0,6);
        System.out.println(Arrays.toString(array));
    }


    /**
     * 跑一半死循环，待查改
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1)) - (o1.get(0)+o1.get(1));
            }
        });
        for(int i = 0;i<Math.min(nums1.length,k);i++){
            for(int j = 0;j<Math.min(nums2.length,k);j++){
                if(maxHeap.size()<k){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    maxHeap.offer(list);
                }else{
                    int top = maxHeap.peek().get(0)+ maxHeap.peek().get(1);
                    if(top > nums1[i]+nums2[j]){

                        maxHeap.poll();

                        List<Integer> list = new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        maxHeap.offer(list);
                    }
                }
            }
        }
        List<List<Integer>> ret = new ArrayList<>();
        for(int i = 0;i<k && !maxHeap.isEmpty();i++){
            ret.add(maxHeap.poll());
        }
        return ret;
    }


}
